The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (i.e., conventional) computers. In 1994, however, Peter Shor showed that for sufficiently large N a quantum computer would be expected to perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the non-expert readers of this journal: (i) the RSA encryption protocol; (ii) the various quantum computer manipulations constituting the Shor algorithm; (iii) how the Shor algorithm performs the factoring; and (iv) the precise sense in which a quantum computer employing Shor's algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer can. It is made apparent that factoring $N$ generally requires many successive runs of the algorithm. The careful analysis herein reveals, however, that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.
展开▼
机译：通过广泛使用的RSA公钥加密系统编码的消息的安全性取决于使用经典（即常规）计算机找到大量N的主要因素所需的巨大计算量。然而，在1994年，彼得·索尔（Peter Shor）表明，对于足够大的N，一台量子计算机将有望以更少的计算量来执行分解。本文力求以本期刊的非专业读者可以理解的方式解释：（i）RSA加密协议； （ii）构成Shor算法的各种量子计算机操作； （iii）Shor算法如何执行分解； （iv）可以说采用Shor算法的量子计算机可以以比传统计算机更少的计算量来完成非常大数量分解的精确意义。显而易见的是，分解$ N $通常需要算法的许多连续运行。然而，本文的仔细分析揭示了在单次运行中成功进行因式分解的可能性大约是文献中通常引用的两倍。
展开▼
